package leetcode.offer_two_special.backtrack;

import java.util.*;
import java.util.function.BiConsumer;

/**
 * @author mazouri
 * @create 2021-09-25 21:03
 */
public class _377_combinationSum4 {
    Map<Integer, Integer> map = new HashMap<>();

    public int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);
        return backtrack(nums, target);

    }

    private int backtrack(int[] nums, int remains) {
        if (remains == 0) return 1;
        if (map.containsKey(remains)) return map.get(remains);

        int res = 0;
        for (int num : nums) {
            if (remains >= num) res += backtrack(nums, remains - num);
        }

        map.put(remains, res);
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new _377_combinationSum4().combinationSum4(new int[]{1, 2, 3}, 3));

    }
}
